//
// Created by Administrator on 2021/11/15.
//
typedef int ElemType;
typedef struct {
    //查找表的数据结构(顺序表)
    ElemType *elem;//动态数组基址
    int TableLen;//表的长度
} SSTable;

/*顺序查找（无哨兵）*/
int Search_Seq(SSTable ST, ElemType key) {
    int i;
    for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);
    return i == ST.TableLen ? -1 : i;//查找成功，则返回元素下标;查找失败，则返回-1
}

/*顺序查找（有哨兵）
 * 将0号位空出来，存放关键字*/
int Search_Seq_with_Sentinel(SSTable ST, ElemType key) {
    ST.elem[0] = key;//"哨兵”
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i); //从后往前找
    return i;//查找成功，则返回元素下标;查找失败，则返回0
}
/*一个成功结点的查找长度=自身所在层数
 * 一个失败结点的查找长度=其父节点所在层数
 * 默认情况下，各种失败情况或成功情况都等概率发生
 * */
/*********************************************************************/
/*折半查找（升序）*/
int Binary_Search(SSTable L, ElemType key) {
    int low = 0;
    int high = L.TableLen - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;//取中间位置
        if (L.elem[mid] == key) {
            return mid;//查找成功则返回所在位置
        } else if (L.elem[mid] > key) {
            high = mid - 1;//从前半部分继续查找
        } else {
            low = mid + 1;//从后半部分继续查找
        }
    }
    return -1;//查找失败，返回-1
}
/*B树（满足以下所有条件）
 * 例如：m叉查找树
 * 策略: m叉查找树中，规定除了根节点外，任何结点至少有「m/21个分叉，即至少含有[m/21 - 1个关键字
 * 策略: m叉查找树中，规定对于任何一个结点，其所有子树得高度都要相同。
*/
/*B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:
1)树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2)若根结点不是终端结点，则至少有两棵子树。
3)除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字。
5)所有的叶结点都出现在同一层次上,并且不带信息
 (可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。
*/

/*m阶B树的核心特性:
1)根节点的子树数∈[2, m],关键字数∈[1, m-1]。其他结点的子树数∈[m/2], m];关键字数∈[[m/2]-1, m-1]
2)对任一结点，其所有子树高度都相同
3)关键字的值:子树0<关键字1<子树1<关键字2<子树2.... (类比二叉查找树左<中<右)
*/

/*注:大部分学校算B树的高度不包括叶子结点(失败结点)
 * 问题:含n个关键字的m阶B树，最小高度、最大高度是多少?
 * 最小高度——让每个结点尽可能地满，有m-1个关键字，m个分叉，则有n≤(m- 1)(1 +m+m^2+m^3+...+m^(h-1))= m^h- 1
 * 因此h≥log[m](n+1)
 *
 * 最大高度一让各 层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有[m/2]个分叉各层结点至少有:
 * 第一层1、第二层2、第三层2「m/2] ... 第h层2([m/2])^(h-2),第h+1层共有叶子结点(失败结点) 2([m/2])^(h-1)个
n个关键字的B树必有n+1个叶子结点，则n+1≥2([m/2])^(h-1),即h≤log[m/2]([(n+1)/2]+1)

*/